Traversing Diagonals

Published

December 21, 2023

This page contains an coding algorithm to iterate the diagonals of a matrix.

Given a matrix of (n_rows, n_cols), there are 4 directions to iterate its diagonals.

From top left to bottom right.
From bottom right to top left.
From top right to bottom left.
From bottom left to top right.

For example, a matrix of 3 rows and 4 cols has 6 diagonals.

Matrix:

      0 1 2 3
    0 0 1 2 3
    1 4 5 6 7
    2 8 9 a b

Iterate the diagonals from top left to bottom right:

    0
    1 4
    2 5 8
    3 6 9
    7 a
    b

Iterate the diagonals from bottom left to top right:

    2
    1 8
    4 9
    0 5 a
    1 6 b
    2 7
    3

Also, for each diagonal, there are 2 ways to iterate its values.

From top to bottom.
From bottom to top

Iterate the diagonals from top left to bottom right and iterate values in each diagonal from top to bottom:

    0
    1 4
    2 5 8
    3 6 9
    7 a
    b

Iterate the diagonals from top left to bottom right and iterate values in each diagonal from bottom to top:

    0
    4 1
    8 5 2
    9 6 3
    a 7
    b

Therefore there are in total of 8 combinations to traverse the diagonals of a matrix. Here we present a systematic way to cover all combinations.

Code

matrix = [
    ['0', '1', '2', '3'], 
    ['4', '5', '6', '7'], 
    ['8', '9', 'a', 'b']
]

Observation

For the diagonals that span from top right to bottom left, which are also the diagonals that we iterate from top left to bottom right, the sum of row index and col index (i + j) is the same for all cells in the same diagonal.

For the example above, the sums of the row index and col index are

      0 1 2 3
    0 0 1 2 3
    1 1 2 3 4
    2 2 3 4 5

Therefore we can iterate through the diagonals and calculate the indices based on this observation.

Algorithm and explanations

top left to bottom right + top to bottom

First we present the algorithm to iterate the diagonals from top left to bottom right. Then we generalize this algorithm to cover other directions.

Outer loop: iterate diagonals from top left to bottom right using d as the index of the diagonal.
```
for d in range(n_rows + n_cols - 1):
```
Since there are num_diags = n_rows + n_cols - 1 number of diagonals, the range of d starts with 0 and ends with num_rows + n_cols - 1.
Inner loop: iterate the elements in each diagonal using i as the row index.
```
for i in range(max(0, d - (n_cols - 1)), min(n_rows, d + 1)):
```
Calculate j index: as the elements in each diagonal are iterated using the row indices, their col indices j can also be calculated.
```
j = d - i
```
This is because the observation above that i + j = d.

Code

n_rows = len(matrix)
n_cols = len(matrix[0])
for d in range(n_rows + n_cols - 1):
    for i in range(max(0, d - n_cols + 1), min(n_rows, d + 1)):
        j = d - i
        print(matrix[i][j], end=" ")
    print()

Reverse the `range` of `d`

By putting reversed to the range of d, you can change the iteration of diagonals from

from top left to bottom right to from bottom right to top left,
from top right to bottom left to from bottom left to top right.

for d in reversed(range(n_rows + n_cols - 1)):

Code

n_rows = len(matrix)
n_cols = len(matrix[0])
for d in reversed(range(n_rows + n_cols - 1)):
    for i in range(max(0, d - n_cols + 1), min(n_rows, d + 1)):
        j = d - i
        print(matrix[i][j], end=" ")
    print()

Reverse the `range` of `i`

By putting reversed to the range of i, you can reverse the iteration of the elements in each diagonal.

for i in reversed(range(max(0, d - (n_cols - 1)), min(n_rows, d + 1))):

Code

n_rows = len(matrix)
n_cols = len(matrix[0])
for d in reversed(range(n_rows + n_cols - 1)):
    for i in reversed(range(max(0, d - n_cols + 1), min(n_rows, d + 1))):
        j = d - i
        print(matrix[i][j], end=" ")
    print()

Reverse `j`

By “reverse” j, you can change the iteration of diagonals from

from top left to bottom right to from top right to bottom left,
from bottom right to top left to from bottom left to top right.

j = n_cols - 1 - (d - i)

Code

n_rows = len(matrix)
n_cols = len(matrix[0])
for d in reversed(range(n_rows + n_cols - 1)):
    for i in reversed(range(max(0, d - n_cols + 1), min(n_rows, d + 1))):
        j = n_cols - 1 - (d - i)
        print(matrix[i][j], end=" ")
    print()

Observation

Algorithm and explanations

top left to bottom right + top to bottom

Reverse the range of d

Reverse the range of i

Reverse j

Reverse the `range` of `d`

Reverse the `range` of `i`

Reverse `j`